home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 / Ham Radio 2000.iso / ham2000 / bbs / lzhuf / lzhuf_1.c < prev    next >
Text File  |  1996-03-02  |  23KB  |  727 lines
  1. /**************************************************************
  2.         lzhuf.c used in F6FBB BBS software
  3.         written by Haruyasu Yoshizaki 11/20/1988
  4.         some minor changes 4/6/1989
  5.         comments translated by Haruhiko Okumura 4/7/1989
  6.         adapatation and additions made by F6FBB - Jean-Paul ROUBELAT
  7. **************************************************************/
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #include <ctype.h>
  12.  
  13. /* crctab calculated by Mark G. Mendel, Network Systems Corporation */
  14. static unsigned short crctab[256] = {
  15.     0x0000,  0x1021,  0x2042,  0x3063,  0x4084,  0x50a5,  0x60c6,  0x70e7,
  16.     0x8108,  0x9129,  0xa14a,  0xb16b,  0xc18c,  0xd1ad,  0xe1ce,  0xf1ef,
  17.     0x1231,  0x0210,  0x3273,  0x2252,  0x52b5,  0x4294,  0x72f7,  0x62d6,
  18.     0x9339,  0x8318,  0xb37b,  0xa35a,  0xd3bd,  0xc39c,  0xf3ff,  0xe3de,
  19.     0x2462,  0x3443,  0x0420,  0x1401,  0x64e6,  0x74c7,  0x44a4,  0x5485,
  20.     0xa56a,  0xb54b,  0x8528,  0x9509,  0xe5ee,  0xf5cf,  0xc5ac,  0xd58d,
  21.     0x3653,  0x2672,  0x1611,  0x0630,  0x76d7,  0x66f6,  0x5695,  0x46b4,
  22.     0xb75b,  0xa77a,  0x9719,  0x8738,  0xf7df,  0xe7fe,  0xd79d,  0xc7bc,
  23.     0x48c4,  0x58e5,  0x6886,  0x78a7,  0x0840,  0x1861,  0x2802,  0x3823,
  24.     0xc9cc,  0xd9ed,  0xe98e,  0xf9af,  0x8948,  0x9969,  0xa90a,  0xb92b,
  25.     0x5af5,  0x4ad4,  0x7ab7,  0x6a96,  0x1a71,  0x0a50,  0x3a33,  0x2a12,
  26.     0xdbfd,  0xcbdc,  0xfbbf,  0xeb9e,  0x9b79,  0x8b58,  0xbb3b,  0xab1a,
  27.     0x6ca6,  0x7c87,  0x4ce4,  0x5cc5,  0x2c22,  0x3c03,  0x0c60,  0x1c41,
  28.     0xedae,  0xfd8f,  0xcdec,  0xddcd,  0xad2a,  0xbd0b,  0x8d68,  0x9d49,
  29.     0x7e97,  0x6eb6,  0x5ed5,  0x4ef4,  0x3e13,  0x2e32,  0x1e51,  0x0e70,
  30.     0xff9f,  0xefbe,  0xdfdd,  0xcffc,  0xbf1b,  0xaf3a,  0x9f59,  0x8f78,
  31.     0x9188,  0x81a9,  0xb1ca,  0xa1eb,  0xd10c,  0xc12d,  0xf14e,  0xe16f,
  32.     0x1080,  0x00a1,  0x30c2,  0x20e3,  0x5004,  0x4025,  0x7046,  0x6067,
  33.     0x83b9,  0x9398,  0xa3fb,  0xb3da,  0xc33d,  0xd31c,  0xe37f,  0xf35e,
  34.     0x02b1,  0x1290,  0x22f3,  0x32d2,  0x4235,  0x5214,  0x6277,  0x7256,
  35.     0xb5ea,  0xa5cb,  0x95a8,  0x8589,  0xf56e,  0xe54f,  0xd52c,  0xc50d,
  36.     0x34e2,  0x24c3,  0x14a0,  0x0481,  0x7466,  0x6447,  0x5424,  0x4405,
  37.     0xa7db,  0xb7fa,  0x8799,  0x97b8,  0xe75f,  0xf77e,  0xc71d,  0xd73c,
  38.     0x26d3,  0x36f2,  0x0691,  0x16b0,  0x6657,  0x7676,  0x4615,  0x5634,
  39.     0xd94c,  0xc96d,  0xf90e,  0xe92f,  0x99c8,  0x89e9,  0xb98a,  0xa9ab,
  40.     0x5844,  0x4865,  0x7806,  0x6827,  0x18c0,  0x08e1,  0x3882,  0x28a3,
  41.     0xcb7d,  0xdb5c,  0xeb3f,  0xfb1e,  0x8bf9,  0x9bd8,  0xabbb,  0xbb9a,
  42.     0x4a75,  0x5a54,  0x6a37,  0x7a16,  0x0af1,  0x1ad0,  0x2ab3,  0x3a92,
  43.     0xfd2e,  0xed0f,  0xdd6c,  0xcd4d,  0xbdaa,  0xad8b,  0x9de8,  0x8dc9,
  44.     0x7c26,  0x6c07,  0x5c64,  0x4c45,  0x3ca2,  0x2c83,  0x1ce0,  0x0cc1,
  45.     0xef1f,  0xff3e,  0xcf5d,  0xdf7c,  0xaf9b,  0xbfba,  0x8fd9,  0x9ff8,
  46.     0x6e17,  0x7e36,  0x4e55,  0x5e74,  0x2e93,  0x3eb2,  0x0ed1,  0x1ef0
  47. };
  48.  
  49.  
  50. #define updcrc(cp, crc) ((crc << 8) ^ crctab[(cp & 0xff) ^ (crc >> 8)])
  51.  
  52.  
  53. FILE  *infile, *outfile;
  54. unsigned    long     int  textsize = 0, codesize = 0, printcount = 0;
  55. unsigned    int        crc;
  56. int                    version_1;
  57. char wterr[] = "Can't write.";
  58.  
  59. void Error(char *message)
  60. {
  61.         printf("\n%s\n", message);
  62.         exit(EXIT_FAILURE);
  63. }
  64.  
  65. /********** LZSS compression **********/
  66.  
  67. #define N               2048    /* buffer size */
  68. #define F               60      /* lookahead buffer size */
  69. #define THRESHOLD       2
  70. #define NIL             N       /* leaf of tree */
  71.  
  72. unsigned char
  73.                 text_buf[N + F - 1];
  74. int             match_position, match_length,
  75.                 lson[N + 1], rson[N + 257], dad[N + 1];
  76.  
  77. static int crc_fputc(int c, FILE *outfile)
  78. {
  79.     crc = updcrc(c, crc);
  80.     return(putc(c, outfile));
  81. }
  82.  
  83. static int crc_fgetc(FILE *infile)
  84. {
  85.     int retour = getc(infile);
  86.  
  87.     if (retour != -1) {
  88.         crc = updcrc(retour, crc);
  89.     }
  90.     return(retour);
  91. }
  92.  
  93. void InitTree(void)  /* initialize trees */
  94. {
  95.         int  i;
  96.  
  97.         for (i = N + 1; i <= N + 256; i++)
  98.                 rson[i] = NIL;                  /* root */
  99.         for (i = 0; i < N; i++)
  100.                 dad[i] = NIL;                   /* node */
  101. }
  102.  
  103. void InsertNode(int r)  /* insert to tree */
  104. {
  105.         int  i, p, cmp;
  106.         unsigned char  *key;
  107.         unsigned c;
  108.  
  109.         cmp = 1;
  110.         key = &text_buf[r];
  111.         p = N + 1 + key[0];
  112.         rson[r] = lson[r] = NIL;
  113.         match_length = 0;
  114.         for ( ; ; ) {
  115.                 if (cmp >= 0) {
  116.                         if (rson[p] != NIL)
  117.                                 p = rson[p];
  118.                         else {
  119.                                 rson[p] = r;
  120.                                 dad[r] = p;
  121.                                 return;
  122.                         }
  123.                 } else {
  124.                         if (lson[p] != NIL)
  125.                                 p = lson[p];
  126.                         else {
  127.                                 lson[p] = r;
  128.                                 dad[r] = p;
  129.                                 return;
  130.                         }
  131.                 }
  132.                 for (i = 1; i < F; i++)
  133.                         if ((cmp = key[i] - text_buf[p + i]) != 0)
  134.                                 break;
  135.                 if (i > THRESHOLD) {
  136.                         if (i > match_length) {
  137.                                 match_position = ((r - p) & (N - 1)) - 1;
  138.                                 if ((match_length = i) >= F)
  139.                                         break;
  140.                         }
  141.                         if (i == match_length) {
  142.                                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  143.                                         match_position = c;
  144.                                 }
  145.                         }
  146.                 }
  147.         }
  148.         dad[r] = dad[p];
  149.         lson[r] = lson[p];
  150.         rson[r] = rson[p];
  151.         dad[lson[p]] = r;
  152.         dad[rson[p]] = r;
  153.         if (rson[dad[p]] == p)
  154.                 rson[dad[p]] = r;
  155.         else
  156.                 lson[dad[p]] = r;
  157.         dad[p] = NIL;  /* remove p */
  158. }
  159.  
  160. void DeleteNode(int p)  /* remove from tree */
  161. {
  162.         int  q;
  163.  
  164.         if (dad[p] == NIL)
  165.                 return;                 /* not registered */
  166.         if (rson[p] == NIL)
  167.                 q = lson[p];
  168.         else
  169.         if (lson[p] == NIL)
  170.                 q = rson[p];
  171.         else {
  172.                 q = lson[p];
  173.                 if (rson[q] != NIL) {
  174.                         do {
  175.                                 q = rson[q];
  176.                         } while (rson[q] != NIL);
  177.                         rson[dad[q]] = lson[q];
  178.                         dad[lson[q]] = dad[q];
  179.                         lson[q] = lson[p];
  180.                         dad[lson[p]] = q;
  181.                 }
  182.                 rson[q] = rson[p];
  183.                 dad[rson[p]] = q;
  184.         }
  185.         dad[q] = dad[p];
  186.         if (rson[dad[p]] == p)
  187.                 rson[dad[p]] = q;
  188.         else
  189.                 lson[dad[p]] = q;
  190.         dad[p] = NIL;
  191. }
  192.  
  193. /* Huffman coding */
  194.  
  195. #define N_CHAR          (256 - THRESHOLD + F)
  196.                                 /* kinds of characters (character code = 0..N_CHAR-1) */
  197. #define T               (N_CHAR * 2 - 1)        /* size of table */
  198. #define R               (T - 1)                 /* position of root */
  199. #define MAX_FREQ        0x8000          /* updates tree when the */
  200.                                         /* root frequency comes to this value. */
  201. typedef unsigned char uchar;
  202.  
  203.  
  204. /* table for encoding and decoding the upper 6 bits of position */
  205.  
  206. /* for encoding */
  207. uchar p_len[64] = {
  208.         0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  209.         0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  210.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  211.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  212.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  213.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  214.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  215.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  216. };
  217.  
  218. uchar p_code[64] = {
  219.         0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  220.         0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  221.         0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  222.         0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  223.         0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  224.         0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  225.         0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  226.         0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  227. };
  228.  
  229. /* for decoding */
  230. uchar d_code[256] = {
  231.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  232.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  233.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  234.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  235.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  236.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  237.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  238.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  239.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  240.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  241.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  242.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  243.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  244.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  245.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  246.         0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  247.         0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  248.         0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  249.         0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  250.         0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  251.         0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  252.         0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  253.         0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  254.         0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  255.         0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  256.         0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  257.         0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  258.         0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  259.         0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  260.         0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  261.         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  262.         0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  263. };
  264.  
  265. uchar d_len[256] = {
  266.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  267.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  268.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  269.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  270.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  271.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  272.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  273.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  274.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  275.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  276.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  277.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  278.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  279.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  280.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  281.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  282.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  283.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  284.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  285.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  286.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  287.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  288.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  289.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  290.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  291.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  292.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  293.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  294.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  295.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  296.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  297.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  298. };
  299.  
  300. unsigned freq[T + 1];   /* frequency table */
  301.  
  302. int prnt[T + N_CHAR];   /* pointers to parent nodes, except for the */
  303.                         /* elements [T..T + N_CHAR - 1] which are used to get */
  304.                         /* the positions of leaves corresponding to the codes. */
  305.  
  306. int son[T];             /* pointers to child nodes (son[], son[] + 1) */
  307.  
  308. unsigned getbuf = 0;
  309. uchar getlen = 0;
  310.  
  311. int GetBit(void)        /* get one bit */
  312. {
  313.         int i;
  314.  
  315.         while (getlen <= 8) {
  316.                 if ((i = crc_fgetc(infile)) < 0) i = 0;
  317.                 getbuf |= i << (8 - getlen);
  318.                 getlen += 8;
  319.         }
  320.         i = getbuf;
  321.         getbuf <<= 1;
  322.         getlen--;
  323.         return (i < 0);
  324. }
  325.  
  326. int GetByte(void)       /* get one byte */
  327. {
  328.         unsigned i;
  329.  
  330.         while (getlen <= 8) {
  331.                 if ((i = crc_fgetc(infile)) == 0xffff) i = 0;
  332.                 getbuf |= i << (8 - getlen);
  333.                 getlen += 8;
  334.         }
  335.         i = getbuf;
  336.         getbuf <<= 8;
  337.         getlen -= 8;
  338.         return i >> 8;
  339. }
  340.  
  341. unsigned putbuf = 0;
  342. uchar putlen = 0;
  343.  
  344. void Putcode(int l, unsigned c)         /* output c bits of code */
  345. {
  346.         putbuf |= c >> putlen;
  347.         if ((putlen += l) >= 8) {
  348.                 if (crc_fputc(putbuf >> 8, outfile) == EOF) {
  349.                         Error(wterr);
  350.                 }
  351.                 if ((putlen -= 8) >= 8) {
  352.                         if (crc_fputc(putbuf, outfile) == EOF) {
  353.                                 Error(wterr);
  354.                         }
  355.                         codesize += 2;
  356.                         putlen -= 8;
  357.                         putbuf = c << (l - putlen);
  358.                 } else {
  359.                         putbuf <<= 8;
  360.                         codesize++;
  361.                 }
  362.         }
  363. }
  364.  
  365.  
  366. /* initialization of tree */
  367.  
  368. void StartHuff(void)
  369. {
  370.         int i, j;
  371.  
  372.         for (i = 0; i < N_CHAR; i++) {
  373.                 freq[i] = 1;
  374.                 son[i] = i + T;
  375.                 prnt[i + T] = i;
  376.         }
  377.         i = 0; j = N_CHAR;
  378.         while (j <= R) {
  379.                 freq[j] = freq[i] + freq[i + 1];
  380.                 son[j] = i;
  381.                 prnt[i] = prnt[i + 1] = j;
  382.                 i += 2; j++;
  383.         }
  384.         freq[T] = 0xffff;
  385.         prnt[R] = 0;
  386. }
  387.  
  388.  
  389. /* reconstruction of tree */
  390.  
  391. void reconst(void)
  392. {
  393.         int i, j, k;
  394.         unsigned f, l;
  395.  
  396.         /* collect leaf nodes in the first half of the table */
  397.         /* and replace the freq by (freq + 1) / 2. */
  398.         j = 0;
  399.         for (i = 0; i < T; i++) {
  400.                 if (son[i] >= T) {
  401.                         freq[j] = (freq[i] + 1) / 2;
  402.                         son[j] = son[i];
  403.                         j++;
  404.                 }
  405.         }
  406.         /* begin constructing tree by connecting sons */
  407.         for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  408.                 k = i + 1;
  409.                 f = freq[j] = freq[i] + freq[k];
  410.                 for (k = j - 1; f < freq[k]; k--);
  411.                 k++;
  412.                 l = (j - k) * 2;
  413.                 memmove(&freq[k + 1], &freq[k], l);
  414.                 freq[k] = f;
  415.                 memmove(&son[k + 1], &son[k], l);
  416.                 son[k] = i;
  417.         }
  418.         /* connect prnt */
  419.         for (i = 0; i < T; i++) {
  420.                 if ((k = son[i]) >= T) {
  421.                         prnt[k] = i;
  422.                 } else {
  423.                         prnt[k] = prnt[k + 1] = i;
  424.                 }
  425.         }
  426. }
  427.  
  428.  
  429. /* increment frequency of given code by one, and update tree */
  430.  
  431. void update(int c)
  432. {
  433.         int i, j, k, l;
  434.  
  435.         if (freq[R] == MAX_FREQ) {
  436.                 reconst();
  437.         }
  438.         c = prnt[c + T];
  439.         do {
  440.                 k = ++freq[c];
  441.  
  442.                 /* if the order is disturbed, exchange nodes */
  443.                 if (k > freq[l = c + 1]) {
  444.                         while (k > freq[++l]);
  445.                         l--;
  446.                         freq[c] = freq[l];
  447.                         freq[l] = k;
  448.  
  449.                         i = son[c];
  450.                         prnt[i] = l;
  451.                         if (i < T) prnt[i + 1] = l;
  452.  
  453.                         j = son[l];
  454.                         son[l] = i;
  455.  
  456.                         prnt[j] = c;
  457.                         if (j < T) prnt[j + 1] = c;
  458.                         son[c] = j;
  459.  
  460.                         c = l;
  461.                 }
  462.         } while ((c = prnt[c]) != 0);   /* repeat up to root */
  463. }
  464.  
  465. unsigned code, len;
  466.  
  467. void EncodeChar(unsigned c)
  468. {
  469.         unsigned i;
  470.         int j, k;
  471.  
  472.         i = 0;
  473.         j = 0;
  474.         k = prnt[c + T];
  475.  
  476.         /* travel from leaf to root */
  477.         do {
  478.                 i >>= 1;
  479.  
  480.                 /* if node's address is odd-numbered, choose bigger brother node */
  481.                 if (k & 1) i += 0x8000;
  482.  
  483.                 j++;
  484.         } while ((k = prnt[k]) != R);
  485.         Putcode(j, i);
  486.         code = i;
  487.         len = j;
  488.         update(c);
  489. }
  490.  
  491. void EncodePosition(unsigned c)
  492. {
  493.         unsigned i;
  494.  
  495.         /* output upper 6 bits by table lookup */
  496.         i = c >> 6;
  497.         Putcode(p_len[i], (unsigned)p_code[i] << 8);
  498.  
  499.         /* output lower 6 bits verbatim */
  500.         Putcode(6, (c & 0x3f) << 10);
  501. }
  502.  
  503. void EncodeEnd(void)
  504. {
  505.         if (putlen) {
  506.                 if (crc_fputc(putbuf >> 8, outfile) == EOF) {
  507.                         Error(wterr);
  508.                 }
  509.                 codesize++;
  510.         }
  511. }
  512.  
  513. int DecodeChar(void)
  514. {
  515.         unsigned c;
  516.  
  517.         c = son[R];
  518.  
  519.         /* travel from root to leaf, */
  520.         /* choosing the smaller child node (son[]) if the read bit is 0, */
  521.         /* the bigger (son[]+1} if 1 */
  522.         while (c < T) {
  523.                 c += GetBit();
  524.                 c = son[c];
  525.         }
  526.         c -= T;
  527.         update(c);
  528.         return c;
  529. }
  530.  
  531. int DecodePosition(void)
  532. {
  533.         unsigned i, j, c;
  534.  
  535.         /* recover upper 6 bits from table */
  536.         i = GetByte();
  537.         c = (unsigned)d_code[i] << 6;
  538.         j = d_len[i];
  539.  
  540.         /* read lower 6 bits verbatim */
  541.         j -= 2;
  542.         while (j--) {
  543.                 i = (i << 1) + GetBit();
  544.         }
  545.         return c | (i & 0x3f);
  546. }
  547.  
  548. /* compression */
  549.  
  550. void Encode(void)  /* compression */
  551. {
  552.         int  i, c, len, r, s, last_match_length;
  553.         char *ptr;
  554.  
  555.         crc = 0;
  556.  
  557.         if (version_1)
  558.         {
  559.             /* Reserves two bytes for the CRC */
  560.             if (fwrite(&crc, sizeof crc, 1, outfile) < 1)
  561.                 Error(wterr);   /* output crc of binary */
  562.         }
  563.  
  564.         fseek(infile, 0L, 2);
  565.         textsize = ftell(infile);
  566.         ptr = (char *)&textsize;
  567.         for (i = 0 ; i < sizeof(textsize) ; i++)
  568.             crc_fputc(ptr[i], infile);
  569.  
  570.         if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1)
  571.                 Error(wterr);   /* output size of text */
  572.         if (textsize == 0)
  573.                 return;
  574.         rewind(infile);
  575.         textsize = 0;                   /* rewind and re-read */
  576.         StartHuff();
  577.         InitTree();
  578.         s = 0;
  579.         r = N - F;
  580.         for (i = s; i < r; i++)
  581.                 text_buf[i] = ' ';
  582.         for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  583.                 text_buf[r + len] = c;
  584.         textsize = len;
  585.         for (i = 1; i <= F; i++)
  586.                 InsertNode(r - i);
  587.         InsertNode(r);
  588.         do {
  589.                 if (match_length > len)
  590.                         match_length = len;
  591.                 if (match_length <= THRESHOLD) {
  592.                         match_length = 1;
  593.                         EncodeChar(text_buf[r]);
  594.                 } else {
  595.                         EncodeChar(255 - THRESHOLD + match_length);
  596.                         EncodePosition(match_position);
  597.                 }
  598.                 last_match_length = match_length;
  599.                 for (i = 0; i < last_match_length &&
  600.                                 (c = getc(infile)) != EOF; i++) {
  601.                         DeleteNode(s);
  602.                         text_buf[s] = c;
  603.                         if (s < F - 1)
  604.                                 text_buf[s + N] = c;
  605.                         s = (s + 1) & (N - 1);
  606.                         r = (r + 1) & (N - 1);
  607.                         InsertNode(r);
  608.                 }
  609.                 if ((textsize += i) > printcount) {
  610.                         printf("%12ld\r", textsize);
  611.                         printcount += 1024;
  612.                 }
  613.                 while (i++ < last_match_length) {
  614.                         DeleteNode(s);
  615.                         s = (s + 1) & (N - 1);
  616.                         r = (r + 1) & (N - 1);
  617.                         if (--len) InsertNode(r);
  618.                 }
  619.         } while (len > 0);
  620.         EncodeEnd();
  621.  
  622.         printf("\n");
  623.         if (version_1)
  624.         {
  625.             /* Writes the CRC in the beginning of the file */
  626.             rewind(outfile);
  627.             if (fwrite(&crc, sizeof crc, 1, outfile) < 1)
  628.                 Error(wterr);   /* output crc of binary */
  629.             printf("CRC: %04x\n", crc);
  630.         }
  631.  
  632.         printf("In : %ld bytes\n", textsize);
  633.         printf("Out: %ld bytes\n", codesize);
  634.         printf("Out/In: %.3f\n", (double)codesize / textsize);
  635. }
  636.  
  637. void Decode(void)  /* recover */
  638. {
  639.         char *ptr;
  640.         int  i, j, k, r, c;
  641.         unsigned long int  count;
  642.         unsigned int  crc_read;
  643.  
  644.         if (version_1)
  645.         {
  646.             if (fread(&crc_read, sizeof crc_read, 1, infile) < 1)
  647.                 Error("Can't read");  /* read size of text */
  648.             printf("File CRC  = %04x\n", crc_read);
  649.         }
  650.  
  651.         crc = 0;
  652.  
  653.         textsize = 0;
  654.         ptr = (char *)&textsize;
  655.  
  656.         for (i = 0 ; i < sizeof(textsize) ; i++)
  657.             ptr[i] = crc_fgetc(infile);
  658.         printf("File Size = %d\n", textsize);
  659.  
  660.         if (textsize == 0)
  661.                 return;
  662.  
  663.         StartHuff();
  664.         for (i = 0; i < N - F; i++)
  665.                 text_buf[i] = ' ';
  666.         r = N - F;
  667.         for (count = 0; count < textsize; ) {
  668.                 c = DecodeChar();
  669.                 if (c < 256) {
  670.                         if (putc(c, outfile) == EOF) {
  671.                                 Error(wterr);
  672.                         }
  673.                         text_buf[r++] = c;
  674.                         r &= (N - 1);
  675.                         count++;
  676.                 } else {
  677.                         i = (r - DecodePosition() - 1) & (N - 1);
  678.                         j = c - 255 + THRESHOLD;
  679.                         for (k = 0; k < j; k++) {
  680.                                 c = text_buf[(i + k) & (N - 1)];
  681.                                 if (putc(c, outfile) == EOF) {
  682.                                         Error(wterr);
  683.                                 }
  684.                                 text_buf[r++] = c;
  685.                                 r &= (N - 1);
  686.                                 count++;
  687.                         }
  688.                 }
  689.                 if (count > printcount) {
  690.                         printf("%12ld\r", count);
  691.                         printcount += 1024;
  692.                 }
  693.         }
  694.         printf("%12ld\n", count);
  695.  
  696.         if (version_1)
  697.             printf("Computed CRC = %04x\n", crc);
  698.  
  699. }
  700.  
  701. int main(int argc, char *argv[])
  702. {
  703.         char  *s;
  704.  
  705.         if (argc != 4) {
  706.                 printf("'lzhuf e[1] file1 file2' encodes file1 into file2.\n"
  707.                            "'lzhuf d[1] file2 file1' decodes file2 into file1.\n");
  708.                 return EXIT_FAILURE;
  709.         }
  710.         if ((s = argv[1], strpbrk(s, "D1E1d1e1") == NULL)
  711.          || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
  712.          || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  713.                 printf("??? %s\n", s);
  714.                 return EXIT_FAILURE;
  715.         }
  716.  
  717.         version_1 = (argv[1][1] == '1');
  718.  
  719.         if (toupper(*argv[1]) == 'E')
  720.                 Encode();
  721.         else
  722.                 Decode();
  723.         fclose(infile);
  724.         fclose(outfile);
  725.         return EXIT_SUCCESS;
  726. }
  727.